public class Solution1269 {
    public int numWays(int steps, int arrLen) {
        int mod=1000000007;
        int len=Math.min(steps/2+1,arrLen);
        int[][] f=new int[steps+1][len];
        f[0][0]=1;
        for (int i=1;i<=steps;i++){
            for (int j=0;j<len;j++){
                f[i][j]=f[i-1][j];
                if (j!=0){
                    f[i][j]=(f[i][j]+f[i-1][j-1])%mod;
                }
                if (j!=len-1){
                    f[i][j]=(f[i][j]+f[i-1][j+1])%mod;
                }
            }
        }
        return f[steps][0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1269().numWays(4,2));
    }
}
